/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：HeapSort.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-06
Function List ：
Description   ：Heap Sort
******************************************************/

#include "HeapSort.h"

#define LeftChild(i)  (2 * (i) + 1)

// Static Function Lists
static void Swap(ElementType *Lhs, ElementType *Rhs);
static void PercDown(ElementType A[], int i, int N);

static void Swap(ElementType *Lhs, ElementType *Rhs) {
    ElementType Tmp;

    Tmp = *Lhs;
    *Lhs = *Rhs;
    *Rhs = Tmp;
}

static void PercDown(ElementType A[], int i, int N) {
    int Child;
    ElementType Tmp;

    for (Tmp = A[i]; LeftChild(i) < N; i = Child) {
        Child = LeftChild(i);
        if (Child != N - 1 && A[Child + 1] > A[Child]) {
            ++Child;
        }

        if (Tmp < A[Child]) {
            A[i] = A[Child];
        } else {
            break;
        }
    }

    A[i] =Tmp;
}

void HeapSort(ElementType A[], int N) {
    int i;

    /* BuildHeap */
    for (i = N / 2; i >= 0; --i) {
        PercDown(A, i, N);
    }

    for (i = N - 1; i > 0; --i) {
        /* DeleteMax */
        Swap(&A[0], &A[i]);
        PercDown(A, 0, i);
    }
}

// EOF

